import java.util.Arrays;

//计数排序
public class CountSort {
    public static void main(String[] args) {
        int[] arr = {1,3,12,26,20,6,9,12,56,78};
        countSort(arr);
        System.out.println(Arrays.toString(arr));

    }
    //计数排序
    public static void countSort(int[] elem){
        int min = elem[0];
        int max = elem[0];
        for (int i = 0; i < elem.length; i++) {
            if(elem[i] < min){
                min = elem[i];
            }
            if(elem[i] > max){
                max = elem[i];
            }
        }
        //用一个计数数组来存储下标
        int[] arr1 = new int[max-min+1];
        int tmp = 0;
        for (int i = 0; i < elem.length; i++) {
            tmp = elem[i] - min;
            arr1[tmp]++;
        }
        int num = 0;
        for (int i = 0; i < arr1.length; i++) {
            while (arr1[i] > 0){
                elem[num] = i + min;
                num++;
                arr1[i]--;
            }
        }
    }
}
